package com.haven123.cloudapp.common.data;

import com.alibaba.fastjson.JSON;
import lombok.Getter;

import java.util.Arrays;

/**
 * Created by Tony_Du on 2018/11/6 0006.
 */
public class BTree<Key extends Comparable<Key>, Value> {
    private static final int    M = 10;         //阶数

    @Getter
    Node<Key, Value>    root;           //根节点
    @Getter
    int                 height;         //高度
    @Getter
    int                 size;           //键值对的数目

    public BTree() {
        root = new Node<>(0);
    }

    public Value get(Key key) {
        checkKey(key);
        return search(root, key, height);
    }

    public void put(Key key, Value val) {
        checkKey(key);

        Node<Key, Value> u = insert(root, key, val, height);
        size++;
        if (u == null) {
            return;
        }

        Node<Key, Value> newRootNode = new Node<>(2);
        newRootNode.children[0] = new Entry<>(root.children[0].key, null, root);
        newRootNode.children[1] = new Entry<>(u.children[0].key, null, u);
        root = newRootNode;
        height++;
    }

    private void checkKey(Key key) {
        if (key == null) {
            throw new NullPointerException("key must not be null");
        }
    }

    private Value search(Node<Key, Value> node, Key key, int ht) {
        Entry<Key, Value>[] children = node.children;

        if (ht == 0) {
            for (int j = 0; j < node.m; j++) {
                if (equals(key, children[j].key)) {
                    return children[j].val;
                }
            }
        } else {
            for (int j = 0; j < node.m; j++) {
                if (j + 1 == node.m || less(key, children[j + 1].key)) {
                    return search(children[j].next, key, ht - 1);
                }
            }
        }
        return null;
    }

    private Node<Key, Value> insert(Node<Key, Value> node, Key key, Value val, int ht) {
        int j;
        Entry<Key, Value> t = new Entry<>(key, val, null);

        if (ht == 0) {
            for (j = 0; j < node.m; j++) {
                if (less(key, node.children[j].key)) {
                    break;
                }
            }
        } else {
            for (j = 0; j < node.m; j++) {
                if ((j + 1 == node.m) || less(key, node.children[j + 1].key)) {
                    Node<Key, Value> u = insert(node.children[j++].next, key, val, ht - 1);
                    if (u == null){
                        return null;
                    }
                    t.key = u.children[0].key;
                    t.next = u;
                    break;
                }
            }
        }

        if (node.m - j >= 0) {
            System.arraycopy(node.children, j, node.children, j + 1, node.m - j);
        }
        node.children[j] = t;
        node.m++;
        if (node.m < M) {
            return null;
        } else {
            return split(node);
        }
    }

    private Node<Key, Value> split(Node<Key, Value> oldNode) {
        int m = M / 2;

        Node<Key, Value> newNode = new Node<>(m);
        oldNode.m = m;

        System.arraycopy(oldNode.children, m, newNode.children, 0, m);
        Arrays.fill(oldNode.children, m, oldNode.children.length, null);
        return newNode;
    }

    private boolean equals(Key k1, Key k2) {
        return k1.compareTo(k2) == 0;
    }

    private boolean less(Key k1, Key k2) {
        return k1.compareTo(k2) < 0;
    }

    public static void main(String[] args) {
        BTree<Integer, Integer> bTree = new BTree<>();
        for (int i = 1; i <=100; i++) {
            bTree.put(i, i);
        }
        System.out.println(JSON.toJSONString(bTree));

        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(JSON.toJSONString(arr));
        System.arraycopy(arr, 4, arr, 5, 5);
        System.out.println(JSON.toJSONString(arr));

        Entry<String, String>[] children = new Entry[5];
    }

    private static final class Node<Key extends Comparable<Key>, Value> {
        @Getter
        int                 m;              //子节点数
        @Getter
        Entry<Key, Value>[] children;       //子节点

        private Node(int m) {
            this.m = m;
            this.children = new Entry[M];
        }
    }

    private static final class Entry<Key extends Comparable<Key>, Value> {
        @Getter
        Key                 key;
        @Getter
        Value               val;
        @Getter
        Node<Key, Value>    next;           // 指向节点中下一元素

        private Entry(Key key, Value val, Node<Key, Value> next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }
}
